package leecode.二叉树;

/**
 * @author wangxi created on 2022/6/8 17:50
 * @version v1.0
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 *
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的 循环 双向链表。
 * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
 */
public class TreeToDoublyList {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    class Solution {
        Node pre = null;
        Node head = null;

        public Node treeToDoublyList(Node root) {
            if (root == null) {
                return null;
            }
            dfs(root);
            // 这里如果使用root节点当做最后一个节点进行收尾连接时，会出现最后一个节点被覆盖了
            // 在dfs这个方法最后一次return时，也是一次出栈，root此时会指向最后一个节点的上一个节点
            pre.right = head;
            head.left = pre;
            return head;
        }

        private void dfs(Node root) {
            if (root == null) {
                return;
            }
            dfs(root.left);
            if (pre == null) {
                pre = root;
                head = root;
            } else {
                root.left = pre;
                pre.right = root;
                pre = root;
            }
            dfs(root.right);
        }
    }
}
